Internet Info 1994 March/Internet Info CD-ROM (Walnut Creek) (March 1994).iso/inet/ien/ien-31

Text File | 1988-12-01 | 27KB | 625 lines

IEN #31
                 On Names, Addresses and Routings (II)

Dan Cohen
ISI
28 April 1978


            2.3.3.11  On Names, Addresses and Routings (II)


SUMMARY

This note deals with internetwork addressing and routing.

It suggests the following:

     (1)  Some systems have a tree-like  hierarchical  Universal-Address
          (UA) space.

     (2)  The communication connectivity is a superset of this tree.

     (3)  The postal system, the telephone  and  the  ARPANET  are  such
          systems.

     (4)  The address of  a  process  tells  where  it  is  located  (or
          connected  to)  by specifying the route to it from the root of
          the universal addressing tree.

     (5)  The default routing to any address (unless  a  better  one  is
          specifically  known)  is  up the UA-tree, from the source, and
          down the tree to the destination.

          In the case of networks like the ARPANET, the set of  all  the
          IMPs  (the subnet) is considered as a single process, known as
          {ARPANET}.

     (6)  Since the set of all networks is not connected, it  cannot  be
          tree  structured.   However, for ease of name-management it is
          possible to introduce (e.g., administratively)  any  arbitrary
          hierarchy   to  the  address  space  of  all  networks.   This
          hierarchy is "artificial" because it is not a  subset  of  the
          communication connectivity.

     (7)  Since there is no hierarchical structure to the space  of  all
          networks,  there  is  no  tree-like  hierarchical internetwork
          Universal-Addressing scheme.

          In particular, the notion of extending addresses like

            {NET}-[HOST]-(PORT) or {NET}-/IMP/-[HOST]-(PORT)

                                     2



          upward to include METANETs,  SUPERNETs  and  GIGANETs  suffers
          from   the  lack  of  corresponding  underlying  communication
          structure.

     (8)  Since the set of all networks is too big  to  be  captured  in
          local  tables,  and since routing cannot be derived in general
          from the addresses, it should always either be apriori  known,
          or  supplied  by  the source.  This apriori knowledge does not
          include every step (e.g., the sequence of intermediate IMPs or
          PRUs).   It  has  to include only a sequence of addresses such
          that the routing between them is locally known.

     (9)  The corollary of this note is

          OPTIONAL  SOURCE  ROUTING  SHOULD  BE  IMPLEMENTED.

This note explains in great detail several  aspects  of  the  addressing
schemes  used by the postal and telephone systems.  It also mentions the
ARPANET addressing.

These examples are used to support the arguments which are summarized in
paragraphs (1)-(9) above.

Unless one is very interested in the details of these systems and  their
relevance  to  the  internetwork  environment,  or in the details of the
arguments, there is no need to continue reading this  note  beyond  this
point.


INTRODUCTION

Before  discussing  the  internet  addressing/routing  issues   let   us
summarize the basic concepts:

     -    Processes (not hardware pieces) have names and addresses.

     -    A process may have more than one name, and  one  address,
          but addresses and names correspond uniquely to processes.

     -    The name tells WHAT the process is.

     -    The address tells WHERE the process is.

     -    The route tells HOW-TO-GET-THERE.

The last three beautiful definitions are  borrowed  (with  appreciation)
from John Shoch.

More detailed  discussion  of  names  and  addresses  may  be  found  in
"Internetwork   Naming,  Addressing,  and  Routing"  [Internet  Notebook
Section 2.3.3.5, IEN 19] by John Shoch, and in "On Names, Addresses  and
Routings" [Internet Notebook Section 2.3.3.7, IEN 23] by Danny Cohen.

                                     3



Generally the concept of address is well understood, but the concept  of
routing  is  much  more  complex.   Who  performs the address-to-routing
mapping? How is it performed? These and similar problems are  the  topic
of this note.

Most of us are familiar with the postal, the telephone, and the  ARPANET
addressing  schemes.   We  also  have  a  very good understanding of the
routing processes performed for these networks.  In this note we discuss
the   similarity  of  these  addressing  schemes,  and  argue  that  the
internetwork environment violates the basic axiom  which  is  common  to
them,  and  therefore  the internetwork environment requires a different
addressing and routing philosophy.

This is why we have so much trouble with internet addressing  --  it  is
different.  Our experience cannot be used as a model.


ON OTHER ADDRESSING/ROUTING SCHEMES

Three  addressing/routing  schemes  are  discussed:  the   postal,   the
telephone, and the ARPANET schemes.

The postal addressing scheme is a UA-scheme.  It is  defined  for  human
processing, and therefore may tolerate a fair amount of redundancy which
improves the robustness of the scheme with  respect  to  errors  and  to
partial losses (like stains on envelopes).

At the top level of  the  hierarchy  there  is  the  country  name,  and
underneath  it  there  are  as  many  addressing  schemes  as  there are
countries.  Some countries use  ZIP  codes  which  identify  major  post
offices,   and   require  more  information  to  identify  the  terminal
addressee.  Other countries use the ZIP  code  (or  its  equivalent)  to
identify  the  individual  letter-carriers,  and require less additional
information to identify the terminal addressee.  In some cases, a street
address is sufficient.  In others, suite number and names are required.

In summary, the postal addressing tree is of variable depth (or:  postal
addresses  are  of  variable length).  Its top level (the country level)
has a complete connectivity, since every country knows how to route mail
to any other one.

Letters are routed, either directly to the destination or to one of  its
ancestors.   This  is  performed  by  POs  either  directly or via their
ancestors.

Since the address and routing processing is not fully  automated,  human
intelligence  is used for resolving ambiguities, for coping with unknown
addresses, for redundancy handling and the like.  Missing information is
usually  supplied  by  using  common sense and defaults.  As a result, a
great amount of variability in addresses can be tolerated.

For example, while at Tech, I received letters addressed to

                                     4



          Danny          (I was the only Danny there)
          256-80         (The Computer Science Mail-stop)
          91125          (The zip code for Caltech)

I also received letters addressed to:

          Dr. Dan Cohen
          Computer Science, Mail-Stop 256-80
          California Institute of Technology
          Pasadena, California 91125

The first address contains all  the  needed  information,  but  requires
delicate  handling.   If  any  of  the digits is mistyped, there is very
little  chance  that  the  letter  would  be  delivered  to  the   right
destination.   The  second  address,  which  has  about  six  times more
characters, is more robust, and can cope with the multi-Danny situation,
which  (even  though  undesirable)  is  still  very probable.  The terse
address has to be modified if another Danny joins this Mail-Stop.

The phone addressing is considered next.  Like the postal  system,  each
telephone station has a UA.  It always starts with the country code, and
usually continues with a Numbering-Plan-Area (NPA, which is the familiar
Area-Code,  AC),  continues  through  a  Central  Office (CO) number and
terminates with the station number.  Even though the above fields are of
variable  length,  the  total  length never exceeds 12 digits.  However,
when private networks are connected to the universal phone  system,  the
entire address length may exceed this limit.

For example, my current phone number  is  12138221511105,  which  is  14
digits  long.   The  first "1" is the USA code, and the last "105" is my
station (extension) number.

At the top level of  the  hierarchy  there  is  the  country  code,  and
underneath  it  there  are  as  many  addressing  schemes  as  there are
countries.  All  countries  know  how  to  communicate  with  any  other
country.   In  both  systems  addresses  are  of variable length, and by
looking at an arbitrary address one cannot parse it into fields  without
knowing the specifics of each national addressing scheme.

Here are some examples of telephone addresses and their correct  parsing
as COUNTRY-NPA-CO-station:

          1-213-822-1511 (USA, LA)
          44-1-387-3400  (UK, London)
          44-31-332-2424 (UK, Edinburgh)
          44-745-58-3301 (UK, Wales)
          972-4-25-2690  (Israel, Haifa)
          972-67-4-0777  (Israel, Kiryat Shmona)

Obviously, the number of fields to be dialed depends on "distance"  from
the destination.

                                     5



Since the telephone routing is performed by (relatively)  simple  minded
automated  equipment,  no  variability  in  dialing  a number is allowed
(except in very unusual situations).

Like the postal addresses,  phone  dialing  sequences  are  of  variable
length,  as a function of the distance to the destination.  While adding
the country code ("USA") would not hurt either of the  postal  addresses
shown  above,  adding  the  local AC and country code is not allowed for
local phone calls.

The reason is that one does not dial the  address  (telephone  numbers),
but dials the routing! The purpose of the telephone number is to be used
for accounting and for deriving routing, but not for verbatim-dialing.

The actual telephone routing (i.e., hop-by-hop) is  very  efficient  and
deserves   attention.    The   key  to  it  is  the  existence  of  more
communication lines than branches in the UA tree.

The USA is divided into 10 regions, which subsequently are divided  into
sections  and  areas.   The  grouping of areas into sections and regions
cannot be simply deduced from the ACs but has to be  found  by  a  table
lookup  operation.   This is because the ACs were most cleverly assigned
to areas by population size and not geographically like the ZIP codes.

The routing is performed by each center assigning each call  to  a  line
known  to  be  connected (or enroute) to the destination central-office.
This is performed by looking at the first  six  digits  of  the  address
(AC+CO).

If such a line does not exist, then the call is assigned to a line known
to be connected to the principal city of the destination NPA.  If such a
line does not exist either, the call is forwarded to  the  center  above
this one.  Since at the top all regions are interconnected, this process
is guaranteed to terminate.

In addition to the SIX digits recognition, the system is  designed  such
that  in  many  cases  CO  numbers  do  not  conflict across NPAs.  This
eliminated the need to dial an AC of a neighboring town, across a  state
line,  which  is  necessarily  in  a  different  NPA.   This allows, for
example, dialing from Washington, D.C.,  (AC=202)  to  Alexandria,  Va.,
(AC=703) and to Potomac, Md., (AC=301) without dialing the AC.

The third addressing scheme is the one used in the ARPANET.

Addresses on the ARPANET are of processes which are either  NCP-like  in
actual hosts or of other types in "fake" hosts.  It is logical to extend
the address notion "down" to include the port, too.

Conceptually, one can consider the ARPANET as a single process or  as  a
star  network.   The  fact  that this single process is implemented in a
very clever way by a multitude of IMPs is irrelevant, from a  functional
point  of  view.   This  allows treating this entire network as a single
addressable process, the {ARPANET}, if so required.

                                     6



Each IMP knows how to forward messages to any other, and  therefore  all
IMPs constitute the top-level (and the only level) for routing.

In the ARPANET all the connections are between centers  (nodes)  of  the
same  (and  only)  level.  This is in contrast to the telephone network,
which has several levels of centers, partially connected at  all  levels
(except  the  top,  where  they  are fully connected) and also partially
connected between levels.

An ARPANET address is of the form {ARPANET}-[HOST]-(PORT), which one may
consider  as  {ARPANET}-/IMP/-[HOST]-(PORT).  Adding the /IMP/ field may
help in the ARPANET situation, though some generality will be lacking.

This is a valid address, since the {ARPANET}-process (which is  the  set
of  all  IMPs)  can  forward  messages  to all hosts, and hosts can give
messages to PORTs.  Therefore, routing every message up to the {ARPANET}
and then down through the host to the destination port is a good default
routing strategy.


INTERNETWORK ADDRESSING

After this (very)  long  introduction,  let's  return  to  the  Internet
Addressing situation.

But first, let's introduce some more formality:

     *    An address is a string (i.e., an ordered set) of  symbols
          taken   from   a  given  alphabet  (e.g.,  ASCII,  {0,1},
          {1,2,...9,0}).

     *    In a UA tree the level of a given address is its depth in
          the tree.  The level of the address A is denoted by L(A).

     *    Address concatenation (extended to  the  right)  will  be
          used.  The concatenation is denoted by a "-".

     *    If both A1 and A2 are addresses of the  same  process  P,
          then

               (1)  L(A1) and L(A2) may differ, and

               (2)  The addresses (A1)-(X)  and  (A2)-(X)  are
                    necessarily addresses of the same process.

     *    Addresses  should  always  be  decodable  in  a  strictly
          left-to-right sequential manner (prefix coding).

What is the ARPANET address of my mailbox?

In the TENEX environment it is [ISI]-(MAILBOX)-<DANNY>.  But in  another
environment,  in  the  host  [X], it could be [X]-<DANNY>-(MAILBOX).  Or
maybe in the form [X]-/TCP/-(MAIL.DEPO)-<DANNY>.

                                     7



Obviously we want to expand it upwards, to allow for other networks.  We
could simply add in front of these addresses a network field and get

                   {ARPANET}-[ISI]-(MAILBOX)-<DANNY>

and similar addresses.  In other networks the value of the NETWORK-field
may be {PRNET-SF}, {PRNET-BOS}, {SATNET}, etc.

What is the relation between these nets? Do they all belong to the  same
parent like USA or USA-DoD?

This could be a solution, and if adopted my mail address may  be  upward
expanded in the UA scheme to be like:

{GALAXY-573}-[SOLAR.SYS]-(EARTH)-<USA>-{ARPANET}-[ISI]-(MAILBOX)-<DANNY>
With  a  clever use of defaults, the first several fields may be omitted
from most of the intraglobal communication.

The extension of this address upward, to include METANETs, SUPERNETs and
GIGANETs,  is  very  elegant.   This  is the prevailing popular approach
expressed in a series of notes and papers,  such  as  Ken  Harrenstien's
note,   and   various   other  communications  between  the  members  of
[SRI-KL]<NETINFO>FIELD-ADDRESS.LIST.  The  intelligent  reader  probably
has  noticed  by  now  that  this  note  does  not subscribe to the same
philosophy.

This solution suffers from several problems.   What  is  a  network?  Is
every  bus  to  which several processes are connected a network? If not,
why? What is the relation between networks?

In order to stress the difference between the structure of the  internet
address  and  of  the other universal addressing schemes, let's consider
the following example.  One of the ARPANET hosts, [PARC-MAXC],  is  tied
to a private network.  This network is actually a very rich internetwork
environment, with about  14  networks  and  about  400  hosts,  but  for
simplicity let us consider it functionally as a single {XEROX-net}.  One
of the  hosts  on  this  net  is  [RIG],  the  University  of  Rochester
Intelligent  Gateway  to the internal {U-of-R-net}.  This description is
not  accurate,  since  [RIG]  is  actually  connected  directly  to  the
{ARPANET},  not to {XEROX-net}.  But for the sake of the argument let us
assume this connectivity.  We preferred not to use other actual examples
for several reasons.  A poet's-license is nice to have....

One of the hosts on the {U-of-R-net} is, say,  [NOVA-3].   What  is  its
address? Obviously it is

     {ARPANET}-[PARC-MAXC]-{XEROX-Net}-[RIG]-{U-of-R-Net}-[NOVA-3].

By the way, whenever an intermediate host in such a specification (i.e.,
a gateway) is between two networks only, there is no need to specify the
destination network, since it is uniquely defined by context.   However,
this  is  not  a  good practice, since addresses have to be changed when
this host is connected to more networks.

                                     8



What is [ISI]'s address? Obviously {ARPANET}-[ISI].

"Not so!" scream the U-of-R people.  The addresses of  [NOVA-3]  and  of
[ISI] are quite different from the point of view of [NOVA-2].  According
to it, the address of [NOVA-3] is simply  {U-of-R-Net}-[NOVA-3]  but  of
[ISI] is {U-of-R-Net}-[RIG]-{XEROX-Net}- [PARC-MAXC]-{ARPANET}-[ISI].

Who is right? Neither!! Either approach is equally  wrong.   Neither  of
these  addresses  is above the other in the UA scheme.  All the networks
involved in the interconnection of these networks are  of  equal  level,
unless  we  decide  otherwise  for administrative reasons.  The internet
communication environment does not have up-and-down relations, except in
the eyes of some users, which may be very subjective.


INTERNETWORK ADDRESSES ARE DIFFERENT

Telephone stations are always connected to the system network, and their
position  in it dictates their addresses.  Not so with computer networks
which spring into an independent existence until they are interconnected
to  others,  if ever.  Therefore, their addresses cannot be deduced from
their positions (geographically or connection-wise) and vice versa.

Therefore, the network ID is an arbitrary string.  Who  assigns  it  and
makes sure that no conflicts occur? Is it NBS? Jon Postel? Another Czar?

At this point we suggest that:

     *    There is no universal hierarchy of networks, in  contrast
          to the telephone and the postal systems.

     *    There are too many networks to be named and/or  addressed
          in a single flat name/address space.

     *    Therefore, some naming/addressing  hierarchy  has  to  be
          introduced.  However, this addressing tree does not serve
          as  a   basis   (or   underlying   structure)   for   the
          communication connectivity.

     *    Routing cannot be computed from any point  to  any  point
          from the addresses alone.

How should  internetwork  routing  be  performed?  There  are  obviously
several  possibilities.   It could be performed entirely by the networks
involved (i.e., the communication system), by  the  source,  or  by  any
combination of the communication system and the source.

It is always  desirable  to  distribute  the  knowledge  about  possible
destinations to the various centers (gateways?), such that their "sphere
of knowledge" is as large as possible, though uniformity should  not  be
required.   More  knowledge  should  be kept about frequent destinations
than about less frequent ones.

                                     9



Since this information must be limited due to  practicalities  (such  as
finite  storage  and  updating  procedures),  it  is impossible that all
sources always know about all possible destinations.

What should be done about unknown destinations?

Several possibilities may be considered.

     o    Having a `supernet' of default sub destinations with  the
          hope  that  they  know  how to find a way to the terminal
          destination (like the phone and the postal systems),

     o    providing internetwork-wide directory services, or

     o    refusal of service.

Let's consider each of these three possibilities.

Having both <USA>-{ARPANET} and <USA>-{XEROX-Net-3} does  not  guarantee
the  existence  of the path {ARPANET}==<USA>=={XEROX-Net-3}.  Therefore,
the supernet (metanet?) is not a part of  the  underlying  communication
structure as in the phone and postal situations.

In order for this approach to work, one has to create this supernet  and
keep   it   updated   about  all  changes  of  the  entire  internetwork
environment.  Both the storage and the updating procedures  seem  to  be
impractical.

The  second  approach,  the  network-wide-directory-help,  is   a   very
reasonable  one.   It  has a major drawback in the necessity to maintain
centers with indefinite  knowledge  radius.   Note  that  the  telephone
directory  services are structured according to the addressing hierarchy
of NPA-CO, and are not flat as may be  suggested  for  the  internetwork
environment.   In  essence, this second approach has all the problems of
the first one.

The third approach, namely, refusal of service to unknown  destinations,
is  consistent,  to  say  the  least.   Admittedly,  it  seems  like  an
inconvenience to users.  It should be supplemented by ways of "learning"
about the unknown destinations, such that refusal should never occur, or
at most, only in very rare  situations.   Directory  services  could  be
helpful.

Hence, this approach supports serving only  destinations  to  which  the
routing  is  either apriori known or supplied.  Note how similar this is
to the telephone system philosophy.

In summary: The internet routing problem is different from  the  routing
problems of other systems because the internet environment does not have
a communication connectivity which supports a UA scheme,  and  therefore
the  addresses  cannot  support  a  direct address-to-routing mapping by
using only a definite amount of knowledge.

                                    10



I HATE TO ADMIT IT, BUT ...

At the beginning of this note, and in an earlier note, I  used  a  great
line telling that "names tell what the processes are, and addresses tell
where they are." It continues by "routings tell how to get there."

I hate to admit  that  by  now  I  have  some  reservations  about  this
definition.   My  name  is  "Danny."  My address is "ISI." When I was at
Tech, my name was  the  same,  but  the  address  was  different.   This
supports  the  definition.   How  about  the addresses in a broadcasting
media network? When a host changes its position (location) on  the  same
Ethernet,  its address does not change.  Well, maybe these addresses are
not real addresses, according to the definition.  Admittedly, this is an
uncomfortable thought.

I believe that there is a better explanation.  I suggest that an address
is "the canonic routing from the root of the addressing-tree." It sounds
recursive, doesn't it?

To be more precise, an addressing scheme is a hierarchical  organization
of  elements,  with  code assignment such that each element has a unique
set of codes, corresponding to its position in the hierarchy.

The notion that the address tells how-to-get-there from the root of  the
tree  is very similar to the notion that absolute coordinates are really
relative, with respect to the origin.

Since we know (by default) how to get from the source to  the  UA  root,
and since the address tells how to get to the destination from the root,
the address tells how to get from the source to the destination.

Hence, by definition, addresses are routings.

This leaves us only with names and routings.  This should  not  surprise
us  now,  since we already discovered that the telephone system has only
names and routings.

Since the general internet environment does not have  a  hierarchy,  the
notion  of addresses suffers.  Since the addresses are "routing from the
root," and since there is no root of the entire system,  our  conclusion
is that there are no addresses, only names and routing.  In other words,
what we are used to call an address is actually a routing  (even  though
it  is  of higher level than the hop-by-hop routing).  In a well defined
(and tightly  controlled)  environment,  such  as  the  {ARPANET},  this
address/routing  is  a  well  defined  string.  In general, it may be of
indefinite length and structure.

If the destination is in the neighborhood, such as the same network, the
same  nets-cluster,  the same agency (even on different net), the system
may have a built-in knowledge of  how  to  get  to  it.   Otherwise  the
routing information needed should be supplied by the sender.

                                    11



PROPOSAL FOR ADDRESSING AND ROUTING

Our proposal for addressing and routing is as follows:

     *    Establish a UA scheme, of variable level structure.

     *    Disseminate as much knowledge to each participating  node
          as deemed practical.

     *    Allow the option of routing to be included in the headers
          of the messages.

     *    Refuse delivery of messages to a destination with unknown
          routing

     *    Establish internet-directory-assistance service.

The  proper  use  of  the  optional  routing  is  to  supply  a  set  of
subdestinations  which  may  be  as far apart as the networks can handle
without help.  This is very  much  like  source  routing  for  telephone
connections,  where  a  sequence of switching-centers is designated by a
user, but the communication subsystem is free to optimize the hop-by-hop
routing between these centers.

As long as the number of  participating  networks  in  the  internetwork
environment  is  small,  it  is possible to have each of them know about
routing to all the others.  However, we already have a  large  community
of  networks,  including several PRNETs, networks in universities, about
15 networks at Xerox, the commercial and the national ones, many in DoD,
all  the  DEC-Nets,  and  many  others.   In  addition,  each big modern
substantial computing system is a network.

One may be advised to expect the number of networks  to  grow,  and  the
internet connectivity to get more and more obscure.

Therefore, optional source routing seems to be the  most  sensible,  and
the  only,  alternative.  This does not exclude the notion that internet
clusters of any size optimize their internal routing by any scheme,  for
example by ARPANET-like dynamic routing scheme.

We recommend that the optional source routing will be composed  of  self
level-identifying  fields.  Note that this is like the telephone dialing
sequence.

The   self-identifying   fields   could   be   implemented   either   by
codes-exclusion   (like  the  telephone  system)  or  by  identification
subfields.  Obviously these two schemes are equivalent, and  the  choice
between them is just a matter of convenience.